Optimal transportation distances are a fundamental family of parameterizeddistances for histograms. Despite their appealing theoretical properties,excellent performance in retrieval tasks and intuitive formulation, theircomputation involves the resolution of a linear program whose cost isprohibitive whenever the histograms' dimension exceeds a few hundreds. Wepropose in this work a new family of optimal transportation distances that lookat transportation problems from a maximum-entropy perspective. We smooth theclassical optimal transportation problem with an entropic regularization term,and show that the resulting optimum is also a distance which can be computedthrough Sinkhorn-Knopp's matrix scaling algorithm at a speed that is severalorders of magnitude faster than that of transportation solvers. We also reportimproved performance over classical optimal transportation distances on theMNIST benchmark problem.
展开▼
